%%This is a very basic article template.
%%There is just one section and two subsections.
\documentclass{article}
\usepackage{graphicx}
\begin{document}

\title{Ant Colony Optimization: Comparing serial and parallel approaches}

\author{Florian Bacher, Marco Wurzer\\
Alpen-Adria-Universit\"at Klagenfurt}

\maketitle

\section{Introduction}

The main goal of our work was to evaluate how a parallel implementation of
the ``Ant Colony Optimization'' algorithm can perform compared to a serial
approach. For the parallel implementation we used an approach which has been
proposed by Randall et al. in \cite{randall:aco} and which will be described in
the next section.\\
In order to evaluate the performance of our parallel implementation in
comparison to our serial implementation we applied it to various TSP problems
which were taken from TSPLIB \cite{tsplib} with different sizes and compared the
calculation times of both algorithms. These tests have been performed on different systems with different numbers
of processor cores so we could see how the number of available processors
influences the performance of the parallel algorithm.

\section{Parallel Approach}
For the parallel implementation of the ant colony optimization algorithm we used
the ``Parallel Ants''-approach which has been proposed by Randall et al. in
\cite{randall:aco}. The idea of this approach is that each ant is assigned to an
own processor. If the number of ants $m$ is larger than the number of
available processors $P$ the ants are clustered on the processors.\\
The seperate ants are maintained by one master which is responsible for user
input, placing the ants at randomly selected starting points, performing local
and global pheromone updates and producing output.\\
The largest part of the communication between the ants is the maintanance of the
pheromone structures as each ant has an own copy of the pheromone matrix which
has to be updated after each iteration and everytime one of the ants has
selected a new city on its path.\\
The pseudocodes for the master and the slaves are depicted in figures
~\ref{master-pseudocode} and ~\ref{slave-pseudocode} \cite{randall:aco}.

\begin{figure}[htpb]
  \centering
    \includegraphics{img/master-pseudocode.jpg}
  \caption{Pseudocode for Master}
  \label{master-pseudocode}
\end{figure}

\begin{figure}[htpb]
  \centering
    \includegraphics{img/slave-pseudocode.jpg}
  \caption{Pseudocode for Slave}
  \label{slave-pseudocode}
\end{figure}

\section{Test Setup}
To compare the parallel and serial approaches against each other we implemented
both versions in Java, using the Thread library for the parallel version.\\
The parameters for the Ant Colony Optimization algorithm were taken from
\cite{randall:aco}:\\

\begin{tabular}{ l r }
  \textbf{Parameter} & \textbf{Value} \\
  \hline
  $\beta$ & -2 \\
  $\gamma$ & 0.1 \\
  $\rho$ & 0.1 \\
  $m$ & 2 \\
  $Q$ & 100 \\
  $q_0$ & 0.9 \\
  $Iterations$ & 1000 \\
\end{tabular}
\\
\\
The TSP problems were taken from TSPLIB \cite{tsplib}:\\
\\
\begin{tabular}{ l c r }
  \textbf{Name} & \textbf{Size} & \textbf{Best known cost}\\
  \hline
  gr24 & 24 & 1272 \\
  st70 & 70 & 675 \\
  kroA100 & 100 & 21,282 \\
  kroA200 & 200 & 29,368 \\
  lin318 & 318 &  42,029 \\
  pcb442 & 442 &  50,778 \\
  rat575 & 575 &  6773 \\
  d657 & 657 &  48,912 \\
\end{tabular}
\\
\\
The tests were performed on two different systems which are listed below:
\begin{itemize}
  \item \textbf{Setup 1:} 
  	\begin{itemize}
  	  \item Windows 7 64Bit
  	  \item Intel Core2Duo @ 3.15GHz
  	  \item 4GB RAM
  	\end{itemize}
  \item \textbf{Setup 2:} 
  	\begin{itemize}
  	  \item Windows 7 32Bit
  	  \item Intel Core2Duo @ 2.2GHz
  	  \item 2GB RAM
  	\end{itemize}
\end{itemize}

\section{Results}
The performance of the parallel implementation against the serial implementation
has been measured with the speedup-factor which is calculated by dividing the
time the serial version needs to find a solution through the time the parallel
version needs to find the solution ($speedup = t_{serial}/t_{parallel}$).\\
Further the efficiency of the parallel code has been calculated by dividing the
speedup-factor through the number of processers used. ($efficiency =
speedup/P$).\\
\\
The results of the experiment are depicted in figure ~\ref{result-table} and
~\ref{result-diagram}.

\begin{figure}[htbp]
  \centering
    \includegraphics{img/result-table.jpg}
  \caption{Result table of the experiment (Speedup and efficiency)}
  \label{result-table}
\end{figure}

\begin{figure}[htbp]
  \centering
    \includegraphics{img/result-diagram.jpg}
  \caption{Graphical representation of the results}
  \label{result-diagram}
\end{figure}
The results show that the parallel code worked best on the kroa100 problem in
the case of system 1. However from this point the speedup factor decreased with
growing problem sizes. On System 2 the parallel code showed its best
performance at a problem size of 70 where it reached a speedup factor of 1.08
but its overall performance was roughly the same as the serial code.\\
Our hypothesis is that the speedup was not as high as expected due to the
maintenance of the seperate pheromone structure which has to be done by the
master as soon as an ant selected a new city.Therefore it would be interesting 
to see how the speedup factor changes when the number of available processors
increases.\\
More detailed results can be viewed in the document
\textit{experiment-results.xlsx} which also contains a comparison of the
calulated solutions to the best known solutions of the TSP-problems.
\bibliographystyle{abbrv}
\bibliography{references}
\end{document}
